package org.example.code.test2024.eleven;

import java.util.*;

/**
 * @Title: test1119
 * @Author yxy
 * @Package org.example.code.eleven
 * @Date 2024/11/19 09:45
 * @description:
 */
public class test1119 {
    public int longestIncreasingPath(int[][] matrix) {
        int max = Integer.MIN_VALUE;
        int[][] visited = new int[matrix.length][matrix[0].length];
        for(int i = 0; i < matrix.length; i++) {
            for(int j = 0; j < matrix[i].length; j++) {
                max = Math.max(max,fun(matrix,i,j,visited));
            }
        }
        return max;
    }

    private int fun(int[][] matrix, int x, int y,int[][] visited) {
        if(visited[x][y] != 0) return visited[x][y];
        int[] a = {0,0,1,-1};
        int[] b = {1,-1,0,0};
        int MAX = 0;
        for(int i = 0; i <4; i++) {
            int xx = a[i]+x;
            int yy = b[i]+y;
            if(xx>=0&&xx<matrix.length&&yy>=0&&yy<matrix[0].length) {
                if(matrix[xx][yy]>matrix[x][y]) {
                    MAX = Math.max(fun(matrix,xx,yy,visited),MAX);
                }
            }
        }
        visited[x][y] = MAX+1;
        return MAX+1;
    }



    public boolean canCross(int[] stones) {
        Map<Integer, HashSet<Integer>> map = new HashMap<>();
        for(int x:stones){
            map.put(x,new HashSet<>());
        }
        map.get(0).add(0);
        for(int x:stones){
            for(int step:map.get(x)){
                int[] sum = {step-1,step,step+1};
                for(int num:sum){
                    if(num>0&&map.containsKey(x+num)){
                        map.get(x+num).add(num);
                    }
                }
            }
        }
        if(map.get(stones[stones.length-1]).isEmpty()){
            return false;
        }
        return true;
    }

    public boolean canPartition(int[] nums) {
        int sum = Arrays.stream(nums).sum();
        if(sum%2!=0) return false;
        int temp = sum/2;
        boolean[]dp =new boolean[temp+1];
        dp[0] = true;
        for(int num : nums){
            for(int i=temp;i>=num;i--){
                dp[i] = dp[i]||dp[i-num];
            }
        }
        return dp[temp];
    }




    public static void main(String[] args) {
       int[] num = {1,5,11,5};
        test1119 test = new test1119();
        System.out.println(test.canPartition(num));
    }



}
